package com.dy.分类.动态规划._85_最大矩形;

import java.util.Arrays;

/*
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int dp[][] = new int[matrix.length][matrix[0].length];
        int max = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
                }
                int width = dp[i][j];
                for (int k = i; k >= 0; k--) {
                    width = Math.min(width, dp[k][j]);
                    max = Math.max(max, width * (i - k + 1));
                }
            }
        }
        return max;
    }

    public int maximalRectangle3(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int maxArea = 0;
        int cols = matrix[0].length;
        int[] leftLessMin = new int[cols];
        int[] rightLessMin = new int[cols];
        //第i行，j列的高度
        int[] hights = new int[cols];

        //最左边为1的下标
        Arrays.fill(leftLessMin, -1);
        Arrays.fill(rightLessMin, cols);

        for (int row = 0; row < matrix.length; row++) {
            //第i行，col列的高度
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '0') {
                    hights[col] = 0;
                } else {
                    hights[col] = hights[col] + 1;
                }
            }

            //第i行，col列最左侧
            int boundaryLeft = -1;
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '0') {
                    boundaryLeft = col;
                    leftLessMin[col] = -1;
                } else {
                    leftLessMin[col] = Math.max(boundaryLeft, leftLessMin[col]);
                }
            }
            int boundaryRight = cols;
            for (int col = cols - 1; col >= 0; col--) {
                if (matrix[row][col] == '0') {
                    boundaryRight = col;
                    rightLessMin[col] = cols;
                } else {
                    rightLessMin[col] = Math.min(boundaryRight, rightLessMin[col]);

                }
            }

            for (int col = cols - 1; col >= 0; col--) {
                maxArea = Math.max(maxArea, (rightLessMin[col] - leftLessMin[col] - 1) * hights[col]);
            }

        }
        return maxArea;

    }


    public int maximalRectangle4(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int maxArea = 0;
        int cols = matrix[0].length;
        int[] leftLessMin = new int[cols];
        int[] rightLessMin = new int[cols];
        Arrays.fill(leftLessMin, -1); //初始化为 -1，也就是最左边
        Arrays.fill(rightLessMin, cols); //初始化为 cols，也就是最右边
        int[] heights = new int[cols];
        for (int row = 0; row < matrix.length; row++) {
            //更新所有高度
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') {
                    heights[col] += 1;
                } else {
                    heights[col] = 0;
                }
            }
            //更新所有leftLessMin
            int boundary = -1; //记录上次出现 0 的位置
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == '1') {
                    //和上次出现 0 的位置比较
                    //  如： 0 1 0 1 1 1        left -1 0 -1（0） 2 2 2
                    //                              -1 0  -1(0)  2 2 2
                    //      1 1 1 1 1 1
                    leftLessMin[col] = Math.max(leftLessMin[col], boundary);
                } else {
                    //当前是 0 代表当前高度是 0，所以初始化为 -1，防止对下次循环的影响
                    leftLessMin[col] = -1;
                    //更新 0 的位置
                    boundary = col;
                }
            }
            //右边同理
            boundary = cols;
            for (int col = cols - 1; col >= 0; col--) {
                if (matrix[row][col] == '1') {
                    rightLessMin[col] = Math.min(rightLessMin[col], boundary);
                } else {
                    rightLessMin[col] = cols;
                    boundary = col;
                }
            }

            //更新所有面积
            for (int col = cols - 1; col >= 0; col--) {
                int area = (rightLessMin[col] - leftLessMin[col] - 1) * heights[col];
                maxArea = Math.max(area, maxArea);
            }

        }
        return maxArea;

    }


}
